---
title: "武士风度的牛"
created: 2025-11-28
tags:
  - 算法
---

# 武士风度的牛

## 题目 [武士风度的牛](https://www.acwing.com/problem/content/190/)

![[image-491b2ac9.png]]

## 思路分析

已经大成了

照着模版默 一遍过 甚至没有debug的过程

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=160;

int n,m;

char g[N][N];

int d[N][N];

int startx,starty,targetx,targety;

int dx[8]={-2,-1,1,2,2,1,-1,-2};

int dy[8]={1,2,2,1,-1,-2,-2,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && d[x][y]==-1;

}

void bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		if(ux==targetx && uy==targety){

			cout<<d[ux][uy];

			return;

		}

		for(int i=0;i<8;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && (g[nx][ny]=='.' || g[nx][ny]=='H')){

				q.push({nx,ny});

				d[nx][ny]=d[ux][uy]+1;

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>m>>n;

	for(int i=0;i<n;i++){

		cin>>g[i];

	}

	for(int i=0;i<n;i++){

		for(int j=0;j<m;j++){

			if(g[i][j]=='K')

				startx=i,starty=j;

			if(g[i][j]=='H')

				targetx=i,targety=j;

		}

	}

	bfs(startx,starty);

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[抓住那头牛|抓住那头牛]] 🏠 [[00-刷题理模型]] ➡️ [[离开中山路|离开中山路]]